#pragma once
#include<vector>
#include<stack>
#include"get_editor_distance.h"


template<class iterator>
SignedArray<int> getSituationOnDiagonals(const PackOfIterators<iterator>& boundsOfContainers, 
										int editorDistance){

	SignedArray<int> editorDistanceOnDiagonal(2 * editorDistance + 1, editorDistance);
	
	editorDistanceOnDiagonal[0] = maxPrefix(boundsOfContainers);
	for (int currentEditorDistance = 1; currentEditorDistance <= editorDistance; ++currentEditorDistance)
		executeFindingEditorDistanceStep(editorDistanceOnDiagonal, currentEditorDistance, 
		boundsOfContainers);
	return editorDistanceOnDiagonal;
}

template<class iterator>													 
std::vector<EditorState<long long> > getEditorScript(const PackOfIterators<iterator> & boundsOfContainers) {
	int editorDistance = getEditorDistance(boundsOfContainers);
	std::vector<EditorState<long long> > editorScript;
	std::stack<PackOfIterators<iterator> > storeOfStates;
	std::stack<int> storeOfEditorDistanceStates;
	storeOfStates.push(boundsOfContainers);
	storeOfEditorDistanceStates.push(editorDistance);
	while (!storeOfStates.empty()){
		PackOfIterators<iterator> forwardIterators = storeOfStates.top();
		storeOfStates.pop();
		int currentEditorDistance = storeOfEditorDistanceStates.top();
		storeOfEditorDistanceStates.pop();
		PackOfIterators < std::reverse_iterator<iterator> > reverseIterators = getReversedPackOfIterators(forwardIterators);
		int firstSize = forwardIterators.firstEnd - forwardIterators.firstBegin;
		int secondSize = forwardIterators.secondEnd - forwardIterators.secondBegin;
		
		if (currentEditorDistance == 0){
			for (iterator it = forwardIterators.firstBegin; it != forwardIterators.firstEnd; ++it){
				editorScript.push_back({ SAME, *it });
			}
			continue;
		}
		if (currentEditorDistance == 1){
			int currentPrefix = maxPrefix(forwardIterators);
			for (int i = 0; i < currentPrefix; ++i){
				editorScript.push_back({ SAME, *(forwardIterators.firstBegin + i) });
			}
			if (firstSize == secondSize + 1){
				editorScript.push_back({ DELETED, *(forwardIterators.firstBegin + currentPrefix) });
				for (int j = currentPrefix + 1; j < firstSize; ++j)
					editorScript.push_back({ SAME, *(forwardIterators.firstBegin + j) });
			}
			else{
				editorScript.push_back({ ADDED, *(forwardIterators.secondBegin + currentPrefix) });
				for (int j = currentPrefix; j < firstSize; ++j)
					editorScript.push_back({ SAME, *(forwardIterators.firstBegin + j) });
			}
			continue;
		}
		if (firstSize == 0){
			for (iterator it = forwardIterators.secondBegin; it != forwardIterators.secondEnd; ++it){
				editorScript.push_back({ ADDED, *it });
			}
			continue;
		}
		if (secondSize == 0){
			for (iterator it = forwardIterators.firstBegin; it != forwardIterators.firstEnd; ++it){
				editorScript.push_back({ DELETED, *it });
			}
			continue;
		}

		SignedArray<int> forwardDiagonalsSituation = getSituationOnDiagonals(forwardIterators, 
			(currentEditorDistance)/2);
		SignedArray<int> reverseDiagonalsSituation = getSituationOnDiagonals(reverseIterators,
			(currentEditorDistance + 1)/2);
		

		int distanceForShifting = firstSize - secondSize;
		for (int numberDiagonal = -(currentEditorDistance / 2); numberDiagonal <= (currentEditorDistance) / 2;
			++numberDiagonal){
			if (-numberDiagonal + distanceForShifting < -((currentEditorDistance + 1) / 2)
				|| -numberDiagonal + distanceForShifting >(currentEditorDistance + 1) / 2)
				continue;
			if (forwardDiagonalsSituation[numberDiagonal] + reverseDiagonalsSituation[-numberDiagonal + distanceForShifting] >= firstSize 
				&& forwardDiagonalsSituation[numberDiagonal] <= firstSize 
				&& reverseDiagonalsSituation[-numberDiagonal + distanceForShifting] <= firstSize){

				int rightForwardX = forwardDiagonalsSituation[numberDiagonal];
				int rightForwardY = rightForwardX - (numberDiagonal);
				int rightBackX = firstSize - rightForwardX;
				int rightBackY = secondSize - rightForwardY;
				storeOfStates.push({ forwardIterators.firstBegin + rightForwardX, forwardIterators.firstEnd,
					forwardIterators.secondBegin + rightForwardY, forwardIterators.secondEnd });
				storeOfStates.push({ forwardIterators.firstBegin, forwardIterators.firstBegin + rightForwardX,
					forwardIterators.secondBegin, forwardIterators.secondBegin + rightForwardY });
				storeOfEditorDistanceStates.push((currentEditorDistance + 1) / 2);
				storeOfEditorDistanceStates.push(currentEditorDistance / 2);
				break;
			}
		}
	}
	
	return editorScript;
}
